from typing import List


# 全排列
class Solution:
    def func(self, nums: List):
        temp = [m for m in nums]
        result = []

        def dfs(inx):
            if inx == len(nums) - 1:
                result.append(list(temp))
                return
            t = set()
            for i in range(inx, len(temp)):
                if temp[i] in t:
                    continue
                t.add(temp[i])
                temp[i], temp[inx] = temp[inx], temp[i]
                dfs(inx+1)
                temp[i], temp[inx] = temp[inx], temp[i]

        dfs(0)
        return result

    # leetcode 91
    def numEncoding(self, s: str):
        n = len(s)
        dp = [1] + [0] * n
        for i in range(1, n+1):
            if s[i-1] != '0':
                dp[i] += dp[i-1]
            if i > 1 and s[i-2] != 0 and int(s[i-2: i]) <= 26:
                dp[i] += dp[i-2]
        return dp[-1]